package leetcode.treeCode.week3.leetcode_105;

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, 0 , preorder.length -1 , inorder , 0 , inorder.length -1);
    }
    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int val = preorder[preStart];
        TreeNode node = new TreeNode(val);
        int index = findIndex(inorder, inStart, inEnd, val);
        int size  = index - inStart;
        node.left = build(preorder,preStart+1 , preStart+size , inorder , inStart , inStart+size -1);
        node.right = build(preorder , preStart + size +1 , preEnd , inorder , index +1 , inEnd);
        return node;

    }
    private int findIndex(int[] arr, int left, int right, int target) {
        for (int i = left; i <= right; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}